{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## 第7章-支持向量机-软间隔最大化对偶问题\n",
    "\n",
    "**拉格朗日对偶性**  \n",
    "$$\\begin{array}{ll}\n",
    "\\displaystyle \\min_{w,b,\\xi} & \\displaystyle \\frac{1}{2}\\|w\\|^2+C \\sum_{i=1}^N \\xi_i \\\\\n",
    "\\text{ s.t. } & y_i(w \\cdot x_i + b) \\geqslant 1- \\xi, i = 1, \\cdots, N \\\\\n",
    "& \\xi_i \\geqslant 0, i=1, \\cdots, N\n",
    "\\end{array}$$  \n",
    "\n",
    "### 对书中第109页的一句话的理解\n",
    "在求解这个问题之前，首先解释书中第109页的一句话  \n",
    "\n",
    "> 该问题的最优解w是唯一的，但b的解可能不唯一，而是存在一个区间。\n",
    "  \n",
    "<br/><center><img style=\"border-radius: 0.3125em;box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);\" src=\"../../../PhaseFour/Note/image/7-5-Uniqueness-of-W.png\"><br><div style=\"color:orange; border-bottom: 1px solid #d9d9d9;display: inline-block;color: #000;padding: 2px;\">图7-5 w的唯一性</div></center>  \n",
    "\n",
    "&emsp;&emsp;$w$是唯一的，说明得到的分离超平面的斜率是唯一的。从图7-5中可以看到，将支撑超平面平移之后，$\\xi_1+\\xi_2$的和是不变的，平移的范围就是从原始位置，移动到最近的误分类点的距离，记为$b$，所以$b$的解是不唯一的。从本例中推测一下，$\\xi$的解也是不唯一的，但是$\\displaystyle \\sum_{i=1}^N \\xi_i$是不变的，这就是对书中该句话的理解。  \n",
    "&emsp;&emsp;在硬间隔最大化中，解是唯一的，但是在软间隔中，不能说解是唯一的。  \n",
    "\n",
    "### 软间隔最大化对偶问题的可行性\n",
    "原始问题是一个凸优化问题（目标函数是一个凸函数，约束条件是一个凸集）。  \n",
    "$\\displaystyle \\because \\frac{1}{2}\\|w\\|=\\frac{1}{2}w^T \\cdot w$  \n",
    "可知$\\displaystyle \\frac{1}{2}w^T \\cdot w$是一个凸函数。  \n",
    "\n",
    "\n",
    "> $f(x)=x$即是一个凸函数，也是一个凹函数。因为任取两个点，该点连线不在函数的下方，即为凸函数，同理可得也是凹函数。\n",
    "\n",
    "$\\therefore f(\\xi)=\\xi$是一个凸函数，有N个这样的凸函数。  \n",
    "$\\displaystyle \\therefore \\frac{1}{2}\\|w\\|^2+C \\sum_{i=1}^N \\xi_i$是凸函数，即目标函数是凸函数。  \n",
    "$\\because y_i(w \\cdot x_i + b) \\geqslant 1- \\xi \\Rightarrow 1 - \\xi_i - y_i(w \\cdot x_i + b) \\leqslant 0$  \n",
    "&emsp;&emsp;上式是一个超平面，满足超平面一侧的点的条件，即满足线性函数$\\leqslant 0$的点组成的集合就是凸集，同理约束条件$-\\xi_i \\leqslant 0$，这个也是关于$\\xi_i$的线性函数，同样满足该函数的点组成的集合也是凸集。那么$2N$个凸集的交集依然是凸集，所以约束条件对应的可行域依然是一个凸集。那么**在一个凸集上求解一个凸函数的最小值问题，这就是一个凸优化问题**。  \n",
    "&emsp;&emsp;在拉格朗日对偶性（第6章-Logistic回归与最大熵模型-拉格朗日对偶性）中说过，对于凸优化问题来说，对偶问题的解与原始问题的解（目标函数最优值）是相等的，并且满足KKT条件。  \n",
    "\n",
    "### 对偶问题的转换与推导\n",
    "拉格朗日函数：$$\\begin{array}{ll} \n",
    "& L(w,b,\\xi,\\alpha, \\mu) \\\\ \n",
    "= & \\displaystyle \\frac{1}{2}\\|w\\|^2 + C \\sum \\xi_i + \\sum \\alpha_i [1 - \\xi_i - y_i(w \\cdot x_i + b)] + \\sum \\mu_i (-\\xi_i) \\\\  \n",
    "= & \\displaystyle \\frac{1}{2}\\|w\\|^2 + C \\sum \\xi_i - \\sum \\alpha_i [y_i(w \\cdot x_i + b) -1 + \\xi_i] - \\sum \\mu_i \\xi_i\n",
    "\\end{array}$$其中$\\alpha_i \\geqslant 0, \\mu_i \\geqslant 0$  \n",
    "下面由拉格朗日函数写出对偶问题，首先分别求出$w,b,\\xi$的梯度，并令梯度等于0：  \n",
    "$$\\begin{array}{ll}\n",
    "\\nabla_w L(w,b,\\xi,\\alpha,\\mu) &= w - \\sum \\alpha_i y_i x_i = 0 \\Rightarrow w = \\sum \\alpha_i y_i x_i \\\\\n",
    "\\nabla_b L(w,b,\\xi,\\alpha,\\mu) &= -\\sum \\alpha_i y_i = 0 \\\\\n",
    "\\nabla_{\\xi_i} L(w,b,\\xi,\\alpha,\\mu) &= C - \\alpha_i - \\mu_i = 0\n",
    "\\end{array}$$  \n",
    "将上述解代入原始问题中，可得$$\\begin{array}{ll} \n",
    "& \\displaystyle \\frac{1}{2}\\|w\\|^2+C \\sum_{i=1}^N \\xi_i \\\\\n",
    "= & \\displaystyle \\frac{1}{2}(\\sum \\alpha_i y_i x_i) \\cdot (\\sum \\alpha_i y_i x_i) + C \\sum \\xi_i - (\\sum \\alpha_i y_i x_i) \\cdot (\\sum \\alpha_i y_i x_i) - b \\sum \\alpha_i y_i + \\sum \\alpha_i - \\sum \\alpha_i \\xi_i - \\sum \\mu_i \\xi_i \\\\\n",
    "= & \\displaystyle -\\frac{1}{2}(\\sum \\alpha_i y_i x_i) \\cdot (\\sum \\alpha_i y_i x_i) + \\sum \\alpha_i \\\\\n",
    "= & \\displaystyle  -\\frac{1}{2} \\sum_i \\sum_j \\alpha_i \\alpha_j y_i y_j (x_i \\cdot x_j) + \\sum \\alpha_i\n",
    "\\end{array}$$  \n",
    "所以对偶问题为$$\\begin{array}{ll} \n",
    "\\displaystyle \\max_\\alpha & \\displaystyle -\\frac{1}{2} \\sum_i \\sum_j \\alpha_i \\alpha_j y_i y_j (x_i \\cdot x_j) + \\sum \\alpha_i \\\\\n",
    "\\text{ s.t. } & \\sum \\alpha_i y_i = 0 \\\\\n",
    "& C-\\alpha_i - \\mu_i = 0 \\\\\n",
    "& \\alpha_i \\geqslant 0 \\\\\n",
    "& \\mu_i \\geqslant 0, i=1,2,\\cdots,N\n",
    "\\end{array}$$  \n",
    "因为原始问题是凸优化问题，解满足KKT条件。  \n",
    "第一个KKT条件为梯度等于0：$$\\begin{array}{ll}\n",
    "\\nabla_w L(w,b,\\xi,\\alpha,\\mu) &= w - \\sum \\alpha_i y_i x_i = 0 \\Rightarrow w = \\sum \\alpha_i y_i x_i \\\\\n",
    "\\nabla_b L(w,b,\\xi,\\alpha,\\mu) &= -\\sum \\alpha_i y_i = 0 \\\\\n",
    "\\nabla_{\\xi_i} L(w,b,\\xi,\\alpha,\\mu) &= C - \\alpha_i - \\mu_i = 0 \n",
    "\\end{array}$$ \n",
    "第二个KKT条件为互补松弛条件：$$\n",
    "\\alpha_i\\big[y_i(w \\cdot x_i + b) - 1 + \\xi_i \\big] = 0 \\\\\n",
    "\\mu_i \\xi_i = 0 $$  \n",
    "第三个KKT条件为原始问题的不等式约束：$$y_i(w \\cdot x_i + b) \\geqslant 1- \\xi \\\\\n",
    "\\xi_i \\geqslant 0 $$ \n",
    "第四个KKT条件为原始问题的等式约束，在这个例子中没有等式约束。  \n",
    "第五个KKT条件是关于拉格朗日乘子的约束条件：$$\\alpha_i \\geqslant 0 \\\\ \n",
    "\\mu_i \\geqslant 0 $$  \n",
    "\n",
    "### 求解（定理7.3）\n",
    "&emsp;&emsp;如果原始问题的最优解为$w^*,b^*,\\xi_i*$，对偶问题的最优解为$\\alpha_i^*, \\mu_i^*$，这些最优解是满足上述KKT条件。  \n",
    "&emsp;&emsp;一旦根据对偶问题求出$\\alpha_i^*$后，可以根据$w = \\sum \\alpha_i y_i x_i$求出$w^*$，求解$b^*$，需要在KKT条件中找到关于$b$的等式约束$\\alpha_i\\big[y_i(w \\cdot x_i + b) - 1 + \\xi_i \\big] = 0$，要求解出$b^*$，必须$\\alpha_i \\neq 0$，又由于$0 < \\alpha_i < C$和$C - \\alpha_i - \\mu_i = 0 \\Rightarrow \\alpha_i = C - \\mu_i < C $，可以得到$\\mu_i > 0 $，代入$\\mu_i \\xi_i = 0$，可以得到$\\xi_i = 0$，再代入公式$\\alpha_i\\big[y_i(w \\cdot x_i + b) - 1 + \\xi_i \\big] = 0$中，得到$y_i(w \\cdot x_i + b) - 1 =0 $，可以得到$b^*$。  \n",
    "&emsp;&emsp;以上解释了为什么需要$\\alpha_i^*$满足$0 < \\alpha_i < C$。## 第7章-支持向量机-软间隔最大化对偶问题\n",
    "\n",
    "**拉格朗日对偶性**  \n",
    "$$\\begin{array}{ll}\n",
    "\\displaystyle \\min_{w,b,\\xi} & \\displaystyle \\frac{1}{2}\\|w\\|^2+C \\sum_{i=1}^N \\xi_i \\\\\n",
    "\\text{ s.t. } & y_i(w \\cdot x_i + b) \\geqslant 1- \\xi, i = 1, \\cdots, N \\\\\n",
    "& \\xi_i \\geqslant 0, i=1, \\cdots, N\n",
    "\\end{array}$$  \n",
    "\n",
    "### 对书中第109页的一句话的理解\n",
    "在求解这个问题之前，首先解释书中第109页的一句话  \n",
    "\n",
    "> 该问题的最优解w是唯一的，但b的解可能不唯一，而是存在一个区间。\n",
    "  \n",
    "<br/><center><img style=\"border-radius: 0.3125em;box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);\" src=\"../../../PhaseFour/Note/image/7-5-Uniqueness-of-W.png\"><br><div style=\"color:orange; border-bottom: 1px solid #d9d9d9;display: inline-block;color: #000;padding: 2px;\">图7-5 w的唯一性</div></center>  \n",
    "\n",
    "&emsp;&emsp;$w$是唯一的，说明得到的分离超平面的斜率是唯一的。从图7-5中可以看到，将支撑超平面平移之后，$\\xi_1+\\xi_2$的和是不变的，平移的范围就是从原始位置，移动到最近的误分类点的距离，记为$b$，所以$b$的解是不唯一的。从本例中推测一下，$\\xi$的解也是不唯一的，但是$\\displaystyle \\sum_{i=1}^N \\xi_i$是不变的，这就是对书中该句话的理解。  \n",
    "&emsp;&emsp;在硬间隔最大化中，解是唯一的，但是在软间隔中，不能说解是唯一的。  \n",
    "\n",
    "### 软间隔最大化对偶问题的可行性\n",
    "原始问题是一个凸优化问题（目标 函数是一个凸函数，约束条件是一个凸集）。  \n",
    "$\\displaystyle \\because \\frac{1}{2}\\|w\\|=\\frac{1}{2}w^T \\cdot w$  \n",
    "可知$\\displaystyle \\frac{1}{2}w^T \\cdot w$是一个凸函数。  \n",
    "\n",
    "\n",
    "> $f(x)=x$即是一个凸函数，也是一个凹函数。因为任取两个点，该点连线不在函数的下方，即为凸函数，同理可得也是凹函数。\n",
    "\n",
    "$\\therefore f(\\xi)=\\xi$是一个凸函数，有N个这样的凸函数。  \n",
    "$\\displaystyle \\therefore \\frac{1}{2}\\|w\\|^2+C \\sum_{i=1}^N \\xi_i$是凸函数，即目标函数是凸函数。  \n",
    "$\\because y_i(w \\cdot x_i + b) \\geqslant 1- \\xi \\Rightarrow 1 - \\xi_i - y_i(w \\cdot x_i + b) \\leqslant 0$  \n",
    "&emsp;&emsp;上式是一个超平面，满足超平面一侧的点的条件，即满足线性函数$\\leqslant 0$的点组成的集合就是凸集，同理约束条件$-\\xi_i \\leqslant 0$，这个也是关于$\\xi_i$的线性函数，同样满足该函数的点组成的集合也是凸集。那么$2N$个凸集的交集依然是凸集，所以约束条件对应的可行域依然是一个凸集。那么**在一个凸集上求解一个凸函数的最小值问题，这就是一个凸优化问题**。  \n",
    "&emsp;&emsp;在拉格朗日对偶性（第6章-Logistic回归与最大熵模型-拉格朗日对偶性）中说过，对于凸优化问题来说，对偶问题的解与原始问题的解（目标函数最优值）是相等的，并且满足KKT条件。  \n",
    "\n",
    "### 对偶问题的转换与推导\n",
    "拉格朗日函数：$$\\begin{array}{ll} \n",
    "& L(w,b,\\xi,\\alpha, \\mu) \\\\ \n",
    "= & \\displaystyle \\frac{1}{2}\\|w\\|^2 + C \\sum \\xi_i + \\sum \\alpha_i [1 - \\xi_i - y_i(w \\cdot x_i + b)] + \\sum \\mu_i (-\\xi_i) \\\\  \n",
    "= & \\displaystyle \\frac{1}{2}\\|w\\|^2 + C \\sum \\xi_i - \\sum \\alpha_i [y_i(w \\cdot x_i + b) -1 + \\xi_i] - \\sum \\mu_i \\xi_i\n",
    "\\end{array}$$其中$\\alpha_i \\geqslant 0, \\mu_i \\geqslant 0$  \n",
    "下面由拉格朗日函数写出对偶问题，首先分别求出$w,b,\\xi$的梯度，并令梯度等于0：  \n",
    "$$\\begin{array}{ll}\n",
    "\\nabla_w L(w,b,\\xi,\\alpha,\\mu) &= w - \\sum \\alpha_i y_i x_i = 0 \\Rightarrow w = \\sum \\alpha_i y_i x_i \\\\\n",
    "\\nabla_b L(w,b,\\xi,\\alpha,\\mu) &= -\\sum \\alpha_i y_i = 0 \\\\\n",
    "\\nabla_{\\xi_i} L(w,b,\\xi,\\alpha,\\mu) &= C - \\alpha_i - \\mu_i = 0\n",
    "\\end{array}$$  \n",
    "将上述解代入原始问题中，可得$$\\begin{array}{ll} \n",
    "& \\displaystyle \\frac{1}{2}\\|w\\|^2+C \\sum_{i=1}^N \\xi_i \\\\\n",
    "= & \\displaystyle \\frac{1}{2}(\\sum \\alpha_i y_i x_i) \\cdot (\\sum \\alpha_i y_i x_i) + C \\sum \\xi_i - (\\sum \\alpha_i y_i x_i) \\cdot (\\sum \\alpha_i y_i x_i) - b \\sum \\alpha_i y_i + \\sum \\alpha_i - \\sum \\alpha_i \\xi_i - \\sum \\mu_i \\xi_i \\\\\n",
    "= & \\displaystyle -\\frac{1}{2}(\\sum \\alpha_i y_i x_i) \\cdot (\\sum \\alpha_i y_i x_i) + \\sum \\alpha_i \\\\\n",
    "= & \\displaystyle  -\\frac{1}{2} \\sum_i \\sum_j \\alpha_i \\alpha_j y_i y_j (x_i \\cdot x_j) + \\sum \\alpha_i\n",
    "\\end{array}$$  \n",
    "所以对偶问题为$$\\begin{array}{ll} \n",
    "\\displaystyle \\max_\\alpha & \\displaystyle -\\frac{1}{2} \\sum_i \\sum_j \\alpha_i \\alpha_j y_i y_j (x_i \\cdot x_j) + \\sum \\alpha_i \\\\\n",
    "\\text{ s.t. } & \\sum \\alpha_i y_i = 0 \\\\\n",
    "& C-\\alpha_i - \\mu_i = 0 \\\\\n",
    "& \\alpha_i \\geqslant 0 \\\\\n",
    "& \\mu_i \\geqslant 0, i=1,2,\\cdots,N\n",
    "\\end{array}$$  \n",
    "因为原始问题是凸优化问题，解满足KKT条件。  \n",
    "第一个KKT条件为梯度等于0：$$\\begin{array}{ll}\n",
    "\\nabla_w L(w,b,\\xi,\\alpha,\\mu) &= w - \\sum \\alpha_i y_i x_i = 0 \\Rightarrow w = \\sum \\alpha_i y_i x_i \\\\\n",
    "\\nabla_b L(w,b,\\xi,\\alpha,\\mu) &= -\\sum \\alpha_i y_i = 0 \\\\\n",
    "\\nabla_{\\xi_i} L(w,b,\\xi,\\alpha,\\mu) &= C - \\alpha_i - \\mu_i = 0 \n",
    "\\end{array}$$ \n",
    "第二个KKT条件为互补松弛条件：$$\n",
    "\\alpha_i\\big[y_i(w \\cdot x_i + b) - 1 + \\xi_i \\big] = 0 \\\\\n",
    "\\mu_i \\xi_i = 0 $$  \n",
    "第三个KKT条件为原始问题的不等式约束：$$y_i(w \\cdot x_i + b) \\geqslant 1- \\xi \\\\\n",
    "\\xi_i \\geqslant 0 $$ \n",
    "第四个KKT条件为原始问题的等式约束，在这个例子中没有等式约束。  \n",
    "第五个KKT条件是关于拉格朗日乘子的约束条件：$$\\alpha_i \\geqslant 0 \\\\ \n",
    "\\mu_i \\geqslant 0 $$  \n",
    "\n",
    "### 求解（定理7.3）\n",
    "&emsp;&emsp;如果原始问题的最优解为$w^*,b^*,\\xi_i*$，对偶问题的最优解为$\\alpha_i^*, \\mu_i^*$，这些最优解是满足上述KKT条件。  \n",
    "&emsp;&emsp;一旦根据对偶问题求出$\\alpha_i^*$后，可以根据$w = \\sum \\alpha_i y_i x_i$求出$w^*$，求解$b^*$，需要在KKT条件中找到关于$b$的等式约束$\\alpha_i\\big[y_i(w \\cdot x_i + b) - 1 + \\xi_i \\big] = 0$，要求解出$b^*$，必须$\\alpha_i \\neq 0$，又由于$0 < \\alpha_i < C$和$C - \\alpha_i - \\mu_i = 0 \\Rightarrow \\alpha_i = C - \\mu_i < C $，可以得到$\\mu_i > 0 $，代入$\\mu_i \\xi_i = 0$，可以得到$\\xi_i = 0$，再代入公式$\\alpha_i\\big[y_i(w \\cdot x_i + b) - 1 + \\xi_i \\big] = 0$中，得到$y_i(w \\cdot x_i + b) - 1 =0 $，可以得到$b^*$。  \n",
    "&emsp;&emsp;以上解释了为什么需要$\\alpha_i^*$满足$0 < \\alpha_i < C$。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.2"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
